package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens {
	List<List<String>> ret;
    List<String> path;
    boolean[] col;  //第i列是否存在元素
    boolean[] dig1; //截距为i的主对角线是否存在元素
    boolean[] dig2; //截距为i的副对角线是否存在元素
    
    
    //获取放置皇后后的当前层信息,该写法建议记号
    public String getString(int n,int pos){
        char[] s=new char[n];
        //先将所有元素填充成'.'
        Arrays.fill(s,'.');
        s[pos]='Q';
        return new String(s);
    }

    //pos: 当前在处理第几层
    public void dfs(int n,int pos){
   
        if(path.size()==n){
            ret.add(new ArrayList(path));
            return ;
        }

        for(int i=0;i<n;i++){
            if(pos==0||(col[i]==false&&dig1[i-pos+n]==false&&dig2[i+pos]==false)){
                path.add(new String(getString(n,i)));
                col[i]=true;
                dig1[i-pos+n]=true;
                dig2[i+pos]=true;
                dfs(n,pos+1);
                //回溯
                path.remove(path.size()-1);
                col[i]=false;
                dig1[i-pos+n]=false;
                dig2[i+pos]=false;
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        ret=new ArrayList<>();
        path=new ArrayList();
        col=new boolean[n];
        dig1=new boolean[2*n];
        dig2=new boolean[2*n];
        dfs(n,0);
        return ret;
    }

}
